package org.banyan.xutlong.sorter;

import java.util.Arrays;

/**
 * Created by think on 2016/2/24.
 * 直接插入排序
 */
public class StraightInsertionSorter extends Sorter {
    @Override
    public void sort(int[] array) {
        int tmp;
        for(int i=1;i<array.length;i++) {
            tmp = array[i];
            // 如果右侧无序区第一个元素array[i] < 左侧有序区最大的array[i-1]，
            // 需要将有序区比array[i]大的元素向后移动。
            if(array[i] < array[i-1]) {
                int j = i - 1;
                // 从右到左扫描有序区
                while (j >= 0 && tmp < array[j]) {
                    array[j + 1] = array[j];
                    // 将左侧有序区中元素比array[i]大的array[j+1]后移
                    j--;
                }
                // 如果array[i]>=左侧有序区最大的array[i-1]，或者经过扫描移动后，找到一个比array[i]小的元素
                // 将右侧无序区第一个元素tmp = array[i]放到正确的位置上
                array[j + 1] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {3,6,4,2,8,13,5};
        StraightInsertionSorter s = new StraightInsertionSorter();
        for (int i=0; i<array.length; i++){
            System.out.print(array[i] + ",");
        }
        System.out.println(array);

        Arrays.sort(array);
    }
}
